Conveniently it is known to use finder patterns to find and identify a wide variety of information on articles and products. Finder patterns are present in most machine readable media, such as common barcodes and two dimensional machine readable codes.
Printed one dimensional barcodes like UPC and Code 39 are well known in the art. They read by electronic sensors scanning along a single line through a printed set of parallel lines of varying width which constitute the code. The information sensed by scanning is passed through logic circuitry which senses the position of codes by detecting starting and stopping positions of code elements along the scan lines and senses timing information to recover size metrics of the code. The characteristics of a code that reveal its position and metrics are commonly referred to as its “finder pattern”. Data content of any codes can only be recovered after the position and metrics of the code are known. In the case of one dimensional codes, the finder pattern design is extremely simple, but typically accounts for 10% or more of the total space occupied by a code. Additionally, one dimensional barcodes are very limited in the amount of data they can carry, and have poor data density.
Many two dimensional codes have been invented to meet the need for larger amounts of data and better data density. Such codes are commonly designed to carry data in a regular rectangular array of elements, much like the older human and mechanical codes like Braille, the player piano scroll, and the punch card. To read such codes with electronic sensing devices requires more sophisticated finder pattern designs that the simple types found in one dimensional codes. Various 2D machine readable code formats like Dot Code A (Phillips Dot Code), PDF-417, Data Matrix, Snowflake and QR-Code are examples of 2D machine readable codes. All of these have specific pattern components to help identify the presence, position, and metrics of the data elements of the code.
As part of their evolution from one dimensional codes, many two dimensional codes have finder patterns that anticipate looking for high contrast line edges with a known sequential spacing pattern detected by scanning along a single scan line (e.g.—PDF-417 and QR). They work well in an environment where the target object is at a known orientation relative to the sensor, and where lighting is well controlled. They are most effective when there is no perspective distortion. Perspective distortion is well known and mathematically understood. In the case of two dimensional surfaces, it occurs when the target surface plane is not perfectly perpendicular to the optical axis or line of sight from the sensor. Such distortion causes a number of problems for processing logic used to identify and locate the finder patterns. For example, points that are equidistant on a target are not typically equidistant in an image under perspective distortion. Also, lines that are parallel on a target will generally not appear to be parallel in an image under perspective distortion. Accordingly, additional algorithmic complexity is required to compensate for the perspective distortions. Although the mathematics of perspective has been well understood for centuries, finder patterns for barcodes have not been designed to easily facilitate correction for this distortion.
U.S. Pat. No. 6,267,296 illustrates a QR finder pattern. The QR finder pattern is an example of a conventional finder pattern, which performs poorly when perspective distortion is present. This pattern is found by recognizing the successive length ratios of light and dark elements along a scan line through large nested-squares patterns in each of three primary corners of a QR code. The method is effective to locate the code when the code is oriented in an un-rotated position and/or the plane of the target is perpendicular to the optical axis of the camera. However, if the QR target is rotated, so that laser scan lines are not perfectly aligned with the rectangular edges of the code, (or equivalently, so that a line of image pixels in a digital camera is not perfectly aligned with the rectangular edges of the code in that image), or if the plane of the target is tilted with respect to the optical axis, then the effectiveness of the finder method substantially decreases. Wide tolerances and/or additional scan line searches must be performed to reliably find the code in different orientations. This added complexity and process steps are disadvantageous.
Most conventional finder patterns are effective under good focus conditions, but rapidly degrade in the presence of blur. For example, U.S. Pat. No. 5,053,609 discloses a Data Matrix code finder pattern. The primary finder pattern of this code includes solid straight line edges on two bounding sides of the code. The edge lines, under good focus conditions, may be detected by identifying points of high gradient value on a series of parallel pixel scan lines through an image. After locating these high-gradient feature points, it is necessary to find two significant subsets of these points that fall predominantly in straight lines. The lines formed by these two subsets are interpreted to be the outer edges of two sides of the full Data Matrix code.
Under blur conditions, high image gradients are strongly attenuated and may appear to be displaced, depending on nearby elements. Blur can be modeled as an optical “circle of confusion” which spreads the light which should ideally be focused on a single point in the image over the entire area of the circle. In this way, light or dark neighboring elements with the circle of confusion can contribute to the observed gradient at the center of the circle. Thus, what might be a point of highest gradient (an “edge”) in a perfectly focused image may not be the point of highest gradient in a blurred image. Specifically, when the diameter of the circle of confusion equals or exceeds the width of the solid line sides of the Data Matrix code, therefore, the location of the feature points can strongly distorted in a way that is dependent on the brightness of nearby points, especially the varying data elements inside the code. The estimated feature point locations may be significantly distorted and may not appear to be colinear. Other common issues like sensor noise, shadows, and lighting gradients, also affect the feature point location estimates. As a result, feature points may appear to lie on a series of broken line segments with varying orientations, rather than the long straight lines that are the edges of the real-world target. Thus, the long edges may not be recognized, or they may not be recognized for their full length and significant error can be introduced into the estimated location and orientation. Long straight line finder patterns which are common in one dimensional codes do not work very well generally with 2D codes.
Finder patterns for 2D codes almost always include a timing pattern. These secondary parts of the finder pattern assist, e.g., in calibrating the number of data elements and the local unit distance for their spacing in an image of the target. A common conventional timing pattern includes a known pattern of alternating contrast elements along one or more lines at specific positions in the target. Such timing patterns are found in QR, Data Matrix, and Snowflake code.
U.S. Pat. No. 5,825,015 illustrates a Snowflake code pattern. The timing pattern includes a fixed pattern of all dots all along one of the two matrix array diagonals. The pattern is used to determine the size of the Snowflake code and is a primary target of a search strategy to find the code. The diagonal, however, uses a large number of dots otherwise available to convey data, and introduces a visually distinct pattern in what would otherwise be a bland field of dots for a human observer. Additional elements of the Snowflake finder pattern include special two-tiered information carrying structures in each corner of the code. In total, the finder pattern for a Snowflake code occupies about a quarter of the total target object area of the code.
QR code also utilizes vertical and horizontal timing patterns between its corner squares. In the more common smaller capacity QR codes, the finder pattern and other fixed elements of the code may occupy nearly half of the target object code area.
Data Matrix code also utilizes timing patterns. These timing patterns constitute the two remaining sides of the code. They consist of an alternating series of small dark and light elements along the borders of the Data Matrix square opposite from the solid straight lines used as an initial finder pattern. (For large code sizes, Data Matrix also introduces additional solid line patterns and timing patterns on the interior of the code.) After an initial estimate of the position of a Data Matrix code is determined by locating the two solid line edges of the code as described before, it is necessary to locate the location and orientation of both timing pattern lines accurately. This is required because the perspective distortion cannot be determined from knowledge of the location and orientation of only two lines. Four lines (or four points) are required. Determining the location and orientation of lines of alternating light and dark modules, especially under blur and shadow conditions, requires a time consuming computational process that typically has poor error characteristics. Data Matrix thus has a poorly designed finder pattern for use in conditions where perspective, blur, and other distortions are likely. Moreover, the timing patterns require a substantial percentage of the available space, thereby limiting the overall data density of the code.
As shown for the foregoing, finder patterns known in the art have a number of disadvantages. They cope poorly with common problems like perspective and blur, and they typically occupy a significant percentage of the target object code area.
In addition, conventional finder patterns, such as the QR, Data Matrix, and Snowflake patterns, are typically visually distinctive graphical elements. Accordingly, the finder patterns are aesthetically objectionable to graphic artists because they tend to clash with product artwork and/or detract from the overall appearance of product packaging. These finder patterns make it difficult to introduce consumer friendly branding or colorful graphic information, e.g., icons, calling attention to intended use or data content. The visual dominance of finder patterns can detract from and limit the effectiveness of iconic information elsewhere on the target. Clearly, they are not appropriate for other related applications such as assisting in machine recognition of symbols, logos, artwork, and general objects in the real-world.
Artistic graphic packaging elements can cause significant technical problems for a decoder by introducing structures that will confuse finder algorithms. For example an icon with a rectangular border near a Data Matrix code or QR code can introduce edges which may be confused with the correct edges of the code. Accordingly, graphics must usually be placed at a considerable distance from all other elements of the code for the finder and data decoding algorithms to work properly.
Moreover, most existing finder patterns form part, or all, of the overall geometric outline of the two-dimensional (2D) code with which they are associated. Accordingly, the finder patterns must typically occur in specific locations, e.g., outside or protruding from the outside, or at the corners of the code, thereby, introducing limitations in the overall shape of codes and in the range of code sizes that are available or practical.
In additional, the conventional finder patterns typically do not work well on non-linear geometries, e.g., a curved enclosure outline or an outline with concave portions. Such flexibility in the overall shape of the machine readable portion of is desirable to create consumer recognizable and consumer friendly codes.